#include <iostream>
#include <utility>
#include <vector>
#include <string>

using namespace std;
class Solution {
public:

    pair<int,int> expand(const string& s,int left,int right){
        while(left > -1 && right < s.size() && s[left] == s[right]){
            left--;
            right++;
        }
        return {left+1,right-1};
    }
    string longestPalindrome(string s) {
        int start = 0;
        int end =0;
        for(int i = 0; i<s.size();i++){
            auto [left1,right1] = expand(s,i,i);
            auto [left2,right2] = expand(s,i,i+1);
            if(right1 - left1 > end-start){
                start = left1;
                end = right1;
            }
            if(right2 - left2> end-start){
                start = left2;
                end   = right2;
            }
        }
        // why?
        // 从start开始的(end-start+1)个的字符
        return s.substr(start,end-start+1);
    }
};